package alo.p6.work;

import org.junit.Test;
import alo.p6.BinaryTreeNode;
//根据前序和中序构造二叉树
    //根据前序遍历和中序遍历的特点
    //前序遍历第一个为根节点，在中序遍历中找到根节点，左边的来自左子树，右边的来自右子树
    //根据这个特点，进行递归
public class BuildBinaryTree {
    static int preIndex=0;
    BinaryTreeNode buildBinaryTree(int[] inOrder, int[] preOrder, int inSta, int inEnd){
        BinaryTreeNode newNode=new BinaryTreeNode();
        if (inSta>inEnd) {
            return null;
        }
        if (newNode==null){
            System.out.println("Memory Error");
            return null;
        }
        //利用preIndex在前序遍历中筛选当前结点
        newNode.setData(preOrder[preIndex]);
        preIndex++;
        //该结点没有孩子
        if (inSta==inEnd){
            return newNode;
        }
        //寻找根节点，确定子树范围
        int inIndex=search(inOrder,inSta,inEnd,newNode.getData());
        //递归
        newNode.setLeft(buildBinaryTree(inOrder,preOrder,inSta,inIndex-1));
        newNode.setRight(buildBinaryTree(inOrder,preOrder,inIndex+1,inEnd));
        return newNode;
    }
    //查找根节点在中序遍历中的索引
    private Integer search(int[] inOrder, int inSta, int inEnd, int data) {
        for (int i=inSta;i<=inEnd;i++){
            if (data==inOrder[i]){
                return i;
            }
        }
        return null;
    }
    @Test
    public void test() {
        int[] A = {1, 2, 4, 5, 3, 6, 7};
        int[] B = {4, 2, 5, 1, 6, 3, 7};
        BuildBinaryTree buildBinaryTree = new BuildBinaryTree();
        BinaryTreeNode root = buildBinaryTree.buildBinaryTree(B, A, 0, 6);
        System.out.println(root);
    }

}
